package com.wtgroup.demo.leetcode.q839_相似字符串组;


import java.util.*;

/**
 * 错误原因:
 * A相似B, B相似C, 但 A不相似C. 如果刚巧, 遍历时遇到 A、C, 再B， A、C 先开辟相似集合. 到B时, 归到要么A要么B所在集合，
 * 实际正确的结果应该是, A、B、C在一个集合中。
 */
public class Solution_err {

    public static void main(String[] args) {
        // String[] strs = new String[]{"tars", "rats", "arts", "star"};
        String[] strs = new String[]{"kccomwcgcs", "socgcmcwkc", "sgckwcmcoc", "coswcmcgkc", "cowkccmsgc", "cosgmccwkc", "sgmkwcccoc", "coswmccgkc", "kowcccmsgc", "kgcomwcccs"};
        // coswmccgkc
        // cosgmccwkc
        // sgckwcmcoc
        new Solution_err().numSimilarGroups(strs);
    }

    public int numSimilarGroups(String[] strs) {

        List<Set<String>> similarSets = new ArrayList<>();
        HashSet<String> set = new HashSet<>();
        set.add(strs[0]);
        similarSets.add(set);

        for (int i = 1, strsSize = strs.length; i < strsSize; i++) {
            String str = strs[i];
            boolean flag = false;
            for (Set<String> similarSet : similarSets) {
                // str 和此集合相似
                if (isSimilar(str, similarSet)) {
                    similarSet.add(str);
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                // 新开一个相似集合容器
                HashSet<String> newSet = new HashSet<>();
                newSet.add(str);
                similarSets.add(newSet);
            }
        }

        System.out.println(similarSets);

        return similarSets.size();
    }


    private boolean isSimilar(String tar, Set<String> set) {
        for (String s : set) {
            if (isSimilar(tar, s)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 要求: 异位词. 长度相同, 字符一样, 只是顺序可能不一样.
     * 最多两处字符不一样.
     * @param a
     * @param b
     * @return
     */
    private boolean isSimilar(String a, String b) {
        char[] aa = a.toCharArray();
        char[] bb = b.toCharArray();
        int k = 0;
        for (int i = 0; i < aa.length; i++) {
            if (k>2) {
                break;
            }
            if (aa[i] != bb[i]) {
                k++;
            }
        }
        return k <= 2;
    }
}
